#include <vector>
#include <assert.h>

typedef unsigned char uint8;

#define PROB_SUM 8096
#define FACTOR (float)(PROB_SUM)
#define DFACTOR (double)(PROB_SUM)
#define INTERVAL_EPSILON 0.01f
#define DECODE_EPSILON 0.001f


struct ProbabilityModel
{
	float  probsMul[256];
	float  probsAdd[256];
	double probsLo[256];
	double probsHi[256];
	uint8 symbolMap[PROB_SUM + 1];

	uint8 GetRandSymbol()
	{
		size_t index = 0;
		for( size_t i = 0; i < 4; ++i )
		{
			index = ( rand() & 255 ) + ( index << 8 );
		}
		return symbolMap[index % PROB_SUM];
	}

	void Init( int probs[256] )
	{
		double probsNor[257];
		probsNor[0] = 0.0;
		size_t cum = 0;

		for( size_t i = 0; i < 256; ++i )
		{
			for( size_t j = cum; j < cum + probs[i]; ++j )
			{
				symbolMap[j] = (uint8)i;
			}

			cum = cum + probs[i];
			probsNor[i + 1] = cum / DFACTOR;
		}

		assert( cum == PROB_SUM );
		
		for( size_t i = 0; i < 256; ++i )
		{
			probsLo[i] = probsNor[i] +  INTERVAL_EPSILON / DFACTOR;
			probsHi[i] = probsNor[i + 1] - INTERVAL_EPSILON / DFACTOR;

			probsMul[i] = (float) ( 1.0 /  ( probsHi[i] - probsLo[i] ) );
			probsAdd[i] = (float)( -probsLo[i] * probsMul[i] * DFACTOR );
		}
	}
};


struct EnCoder
{
	float lo;
	float hi;

	EnCoder() : lo( 0.0f ), hi( FACTOR )
	{
	};

	void DeCode( ProbabilityModel *model, uint8 symbol, std::vector<uint8> &out )
	{		
		float *probsMul = model->probsMul; 
		float *probsAdd = model->probsAdd;
		uint8 *symbolMap = model->symbolMap;

		float s = float( symbol ) / 256.0f;
		float n = float( symbol + 1 ) / 256.0f;
		
		float newLo = hi * s + ( 1.0f - s ) * lo;
		float newHi = hi * n + ( 1.0f - n ) * lo;

		lo = newLo;
		hi = newHi;

		while( 1 )
		{
			lo -= DECODE_EPSILON;
			hi += DECODE_EPSILON;
			
			if( lo < 0.0f )
			{
				lo = 0.0f;
			}

			if( hi > FACTOR )
			{
				hi = FACTOR;
			}

			int indLo = (int)( lo );
			int indHi = (int)( hi );

			uint8 loSymbol = symbolMap[indLo];
			uint8 hiSymbol = symbolMap[indHi];

			if( loSymbol == hiSymbol )
			{
				out.push_back(  loSymbol );
				lo = lo * probsMul[loSymbol] + probsAdd[loSymbol];
				hi = hi * probsMul[loSymbol] + probsAdd[loSymbol];
			}
			else
			{
				return;
			}
		}
	}
};

class DeCoder
{
	EnCoder enCoder;
	ProbabilityModel *model;
	
public:
	DeCoder( ProbabilityModel *_model ) : model( _model )
	{
	};

	void RandomRun()
	{
		std::vector< uint8 > input( 65536 );
		
		std::vector< uint8 > enCoded;	
		std::vector< uint8 > code;
		
		for( size_t i = 0; i < input.size(); ++i )
		{
			input[i] = model->GetRandSymbol();
		}

		for( size_t j = 0; j < input.size();   )
		{
		
			double lo = 0.0f;
			double hi = FACTOR;

			size_t i = j;
			
			while( 1 )
			{
				size_t index = input[i];
				if( i + 1 < input.size() )
				{
					++i;
				}
				double diff = hi - lo;
				
				double newLo = lo + diff * model->probsLo[index]; 
				double newHi = lo + diff * model->probsHi[index];
				
				hi = newHi;
				lo = newLo;
				if( hi < lo + 0.0000001f )
				{
					break;
				}
			}

			double diff = ( enCoder.hi - enCoder.lo );
			int nextCode = int( 256.0 * ( lo - enCoder.lo ) / diff );
			if( nextCode < 0 )
			{
				nextCode = 0;
			}
			if( nextCode > 255 )
			{
				nextCode = 255;
			}

			size_t oldSize = enCoded.size();
			enCoder.DeCode( model, nextCode, enCoded );
			code.push_back( nextCode );
			j += enCoded.size() - oldSize;
		}

		
		size_t unMatchedLiterals = 0;
		enCoded.resize( input.size() );
		for( size_t i = 0; i < input.size() && i < enCoded.size(); ++i )
		{
			//printf("%c%c|", input[i], enCoded[i] );
			if( input[i] != enCoded[i]  )
			{
				++unMatchedLiterals;
			}
		}
		printf( "\n" );
		printf( "unmatched symbols %d \n", unMatchedLiterals );
		printf( "input length %d \n", input.size() );
		printf( "coded length %d \n", code.size() );

	}

};

ProbabilityModel model;

int main( int argc, char* argv[] )
{
	int probs[256];
	for( size_t i = 0; i < 256; ++i )
	{
		probs[i] = 0;
	}
	int pP = int( 0.01892 * PROB_SUM );
	int pe = int( 0.00345 * PROB_SUM );
	int pt = int( 0.50345 * PROB_SUM );
	int pr = PROB_SUM - pP - pe - pt;
	
	probs['P'] = pP;
	probs['e'] = pe;
	probs['t'] = pt;
	probs['r'] = pr;


	model.Init( probs );

	DeCoder deCoder( &model );
	deCoder.RandomRun();
	return 0;

}
